package Heap;

public class _264_UglyNumberII {
    public int nthUglyNumber(int n) {
        //every ugly elements after 5 is the product of before element. ep: 15=3*5,30=2*3*5.
        int[] ugly = new int[n];
        ugly[0] = 1;
        int index1 = 0, index2 = 0, index3 = 0;
        int factor1 = 2, factor2 = 3, factor3 = 5;
        for (int i = 1; i < n; i++) {
            int min = Math.min(Math.min(factor1, factor2), factor3);
            ugly[i] = min;
            if (min == factor1) {
                factor1 = 2 * ugly[++index1];
            }
            if (min == factor2) {
                factor2 = 3 * ugly[++index2];
            }
            if (min == factor3) {
                factor3 = 5 * ugly[++index3];
            }
        }
        return ugly[n - 1];
    }
}
